In a virtual memory system, programs and data are assigned virtual, or logical, addresses, and system users reference the virtual addresses rather than addresses in a physical memory. A significant advantage of a virtual memory processing system is that the virtual, or logical, address space which is available for use by system users may differ from the actual physical space of the processing system's main memory. In such a processing system only a portion of the virtual memory may reside in the physical main memory at any one time, while the remainder may reside in bulk secondary storage. To make the entire virtual memory selectively accessible in main memory, provision must be made for swapping, or transferring, portions of the virtual memory from secondary storage into the physical main memory and from the main memory back into secondary storage as dictated by the demands of system use.
For purposes of memory management, including swapping, the virtual memory is commonly divided into blocks of equal size, called pages, and portions of virtual memory are swapped into and out of main memory in units of one or more pages. The main memory is in turn divided into page frames, each being a hardware component into which a virtual page may be copied. Whenever information contained in a virtual page which is not in main memory is needed, the page is brought in from secondary storage and is stored in a page frame. The number of page frames is limited, however. If all page frames are occupied and yet another page is needed, a page frame is selected and cleared of the page that currently occupies it and the demanded page is transferred into the cleared page frame.
A virtual memory computing system includes a mechanism for translating virtual addresses into corresponding physical, main memory addresses which are utilized by the processor. The translating mechanism commonly includes an address translation buffer (ATB), which is a relatively small and fast memory used for storing selected virtual addresses and the corresponding main memory addresses that were obtained as a result of previous address translations. Since retrieving the result of a previous translation from the ATB is faster than repeating the translation with the translating mechanism, the use of an ATB speeds up the process of accessing items in memory.
The entries of the ATB are generally valid only for the current virtual memory contents of the main memory, to which the main memory address entries of all of the ATBs refer. Hence whenever the virtual memory contents of the main memory are changed by a page swap, ATB entries which are affected by the swap must be flushed. As used herein, "flushing" of a storage element refers to removing, invalidating, clearing, or otherwise destroying the current contents of the storage element.
A processing system has a plurality of processes executing on one or more processors. For example, a number of processes may execute on a single processor on a time shared basis. And a number of processes may execute concurrently, one on each processor of a multiprocessor system. The processes share use of the main memory of the processing system. Such a system may include a plurality of address translation buffers for use by the plurality of processes. Whenever a process causes a page to be swapped into or out of the shared main memory in such a system, care must be taken that entries of all ATBs that are affected by the swap be invalidated. Otherwise another process, unaware of the swap, may utilize an entry of an ATB to access the wrong page of virtual memory, with consequent erroneous results.
The prior art has approached the problem of keeping the plurality of ATB's updated in such systems in a variety of ways. One approach has been to cause the process which initiated the swap to cause a processor to access all ATBs in the system and invalidate therein the entries affected by the swap. However, the overhead involved in searching for and invalidating affected entries in all ATBs adversely impacts system performance. Moreover, the difficulties, expense, and overhead involved in enabling a plurality of processors in a multiprocessor system to access each ATB, and in synchronizing these accesses such that they may be performed in a mutually non-interfering manner, has been great.
Another approach has been for a process which initiated the swap to inform, for example by means of an interrupt, the other processes of the swap so that they could each have the entries of their own ATBs modified accordingly. However, the overhead involved in informing each process not only of the fact that a swap had taken place but also of which pages were affected thereby and in having to search through plural ATBs to find and invalidate the affected entries is so significant as potentially to make paging an unattractive feature in such a system.
A further problem associated with both of the above approaches of the prior art is that of determining whether a page in physical memory that is shared by two or more processes is currently in use by a process, and of preventing another process from having the page swapped out while it is in use. Prior art schemes, such as associating with each page a counter that is incremented each time a page is used by a process, and decremented each time the page ceases to be used by a process, have not been satisfactory, primarily because of the overhead involved in maintaining and in querying such a counter. Moreover, a shared page can be at different virtual addresses in different processes and consequently may correspond to a different entry in each ATB. Substantial difficulty and overhead is involved in determining, or keeping track of, plural identities of a shared page.
Yet another approach taken by the prior art has been to restrict the pages that a process may swap. For example, a process may be restricted to swapping out only those pages that it already owns, i.e., it may remove from physical memory only those pages that it has placed therein, and it may not swap out pages which it shares with other processes. These restrictions are severe in terms of limiting optimal use of the physical memory, and they tend to destroy the concept of shared memory and the benefits derived therefrom.